1. Copyright Notice
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
2. Related Application Data
The present disclosure is related to the disclosures provided in the following U.S. applications filed on even date herewith: "Intelligent System for Generating and Executing a Sheet Metal Bending Plan," filed in the names of David Alan Bourne et al. (U.S. application Ser. No. 08/338,113); "Methods and Apparatuses for Backgaging and Sensor-Based Control of Bending Operations," filed in the names of Richard M. Moore, Jr. et al. (U.S. application Ser. No. 08/338,153); and "Fingerpad Force Sensing System," filed in the names of Anne M. Murray et al. (U.S. application Ser. No. 08/338,095). The contents of each of these related applications are expressly incorporated by reference herein in their entireties.
3. Field of the Invention
The present invention relates to methods for planning/controlling the motion of a robot, and various systems and sub-components related to the operation thereof.
4. Discussion of Background Information
Various methods have been disclosed in the literature for providing a geometric model of the "amount of free space" a robot has to move within, and for producing a motion plan for the robot to move from a start position to a goal position within the free space. Approximate decomposition methods are among such methods for modeling a robot's free space, as disclosed by Jean-Claude Latombe in "Robot Motion Planning," Kluwer Academic Publishers, Boston/Dordrecht/London (1991), the content of which is expressly incorporated herein by reference in its entirety. Approximate cell decomposition may be utilized to determine the amount of free space in a given physical environment. In some such methods, a rectangloid (i.e., a rectangle or parallelepiped) decomposition is formed of .OMEGA.=Cl(), which is a rectangloid of .sup.m, where m is the dimension of the configuration space. The resulting rectangloid decomposition is utilized to search for a solution path connecting a start position Q.sub.init to a goal position Q.sub.goal. An algorithm that may be utilized to find the solution path is as follows:
(1) An initial rectangloid decomposition .sub.i of a rectangloid .OMEGA. within is computed, and cells are thus produced, each of which is classified as: empty, if it does not intersect a C-obstacle region; full, if it is entirely contained in a C-obstacle region; and mixed if it partially intersects a C-obstacle region.
(2) The resulting decomposition .sub.i is searched in order to obtain a channel that connects the initial cell containing Q.sub.init to the goal cell containing Q.sub.goal. The channel may either be an E-channel, comprising all empty cells, or an M-channel, comprising one or more mixed cells. If the outcome of the search is an E-channel, the algorithm will return with the free-space empty cell E-channel. If, however, the outcome of the search is an M-channel, the process will proceed to step (3) below. Otherwise, the algorithm will return with failure.
(3) For every mixed cell within a generated M-channel, a further rectangloid decomposition .sub.i will be computed, and the process will return to step (2).
In computing a rectangloid decomposition of a MIXED cell, a divide-and-label method may be performed, as illustrated in FIG. 1. The method comprises the steps of first dividing a cell into smaller cells, as illustrated in FIG. 1, and then labeling each newly created cell according to whether it intersects a C-obstacle region. A widely used technique for decomposing a rectangloid .OMEGA. into smaller rectangloids is to compute a 2.sup.m -tree decomposition. In a 2.sup.m -tree decomposition, a tree is formed having nodes, each of which represents a rectangloid cell which is labeled as either EMPTY, FULL or MIXED. The root node of the tree is .OMEGA.. Each node which represents a MIXED cell will then be decomposed to form 2.sup.m children nodes. Each child of a parent cell has the same dimensions, and is formed by dividing each edge of the parent cell into two segments of equal length. If m=3, the tree is called an octree.
FIG. 1 shows an octree decomposition of a parallelepiped representation 10 of a portion of configuration space, and displays a portion of an octree graph 12. The overall height h of the tree (i.e., the depth of the deepest node) determines the resolution of the decomposition, and hence the size of the smallest cells in the decomposition. A maximum height h.sub.max of the tree may be specified to thereby limit the iterative process carried out by steps 2 and 3 of the algorithm noted above.
It is noted that octree graph 12 does not correspond precisely to the parallelepiped 10 depicted in FIG. 1. Rather, the various rectangloids depicted in octree graph 12 are chosen randomly in order to simplify the illustration.
The above described approximate cell decomposition method utilizes a configuration space approach to spatial planning, whereby the position and orientation of an object A in relation to obstacles B is characterized as a single point in a configuration space, in which the coordinates of the point represent a degree of freedom of the object in relation to the obstacles. The configurations (i.e., the placements) forbidden to the object A, due to the presence of other objects/obstacles, are characterized as regions in the configuration space, called configuration space obstacles (C-obstacles). Much literature has been published concerning the use of a configuration-space representations of an object with respect to obstacles, including a paper by Tomas Lozano-Perez, entitled "Spatial Planning: A Configuration Space Approach", IEEE Transactions on Computers, Vol. C-32, No. 2 (February 1983), the content of which is expressly incorporated by reference herein in its entirety. This paper presents several algorithms for computing configuration space obstacles formed by objects which are polygons or polyhedra.
FIG. 2A illustrates a two-dimensional representation of a peg 26 and a hole 28, wherein the goal is to place peg 26 within hole 28, so that a bottom surface 27 of peg 26 makes flush contact with a bottom surface g of hole 28. The position and orientation of peg 26 may be represented in two-dimensional euclidian space as a set of Cartesian coordinates (x,y,.theta.), the origin of which is positioned at the center of bottom surface 27 of peg 26. At the location illustrated in FIG. 2A, peg 26 will have the coordinates .theta.=0, x=0, and y =0.
FIG. 2B illustrates a configuration space representation of the real-space problem of FIG. 2A. A point P is shown in its initial position (as shown in FIG. 2B) and may be moved to any position along a portion G of C-surface 29. C-surface 29 represents a C-obstacle 30 that corresponds to an obstacle (hole) 31 represented in real-space in FIG. 2A, and point P represents peg 26.
The position of P determines the position of peg 26 in relation to hole 28. The boundary of the shaded area shown in FIG. 2B represents the positions at which peg 26 would be in contact with obstacle 31, if point P was along the boundary. The transformation from FIG. 2A to FIG. 2B amounts to shrinking the peg 26 to a point P, and expanding obstacle 31 to form a C-obstacle 30. The transformation from FIG. 2A to FIG. 2B is a limited example of how one may reformulate a problem of moving a rigid object among other rigid objects as an equivalent problem of moving a point among transformed objects in a higher-dimensional space called the configuration space (C-space).
It is noted that FIG. 2B corresponds to the points at which peg 26 will collide with obstacle 31, if the axes (x,y) of peg 26 and hole 28 are constrained to be parallel, thereby keeping .theta. equal to 0.
FIG. 2C illustrates how the C-surface changes as the orientation of peg 26, with respect to hole 28, changes, i.e., as .theta. increases from 0 by rotating the orientation of peg 26 in a counter-clockwise direction. FIG. 2C thus shows in a three-dimensional C-space (x,y,.theta.) the configurations of peg 26 with respect to hole 28. In this space, hole 28 is defined as a C-obstacle. The lines illustrated in FIG. 2C represent surfaces at which some surface of peg 26 is just touching a surface of hole 28.
Another approach to motion planning may be utilized by which the configuration is discretized into a fine regular grid of configurations, and is then searched for a free path from an initial position Q.sub.init to a goal location Q.sub.goal. In searching the grid for a free path, several types of heuristics have been proposed. Latombe notes in "Robot Motion Planning" (1991) that the most successful types of heuristics, for searching a fine regular grid of configurations for a free include the use of functions that are interpreted as "potential fields". The functions are called "potential fields" because the robot is represented as a point in configuration space which can be viewed as a particle moving under the influence of an artificial potential produced by the goal configuration (i.e., the point within the configuration space at which the point representing the robot will be at the goal) and the C-obstacles. Typically, the goal configuration generates an "attractive potential" which pulls the robot toward the goal, and the C-obstacles produce a "repulsive potential" which pushes the robot away from them. The direction of the resulting force is considered to be the most promising direction of motion.
In industry, in order to plan the gross motion of a robot which will be utilized to implement a particular process step, the robot is "walked through" the needed movements to bring the robot from a starting position to a goal position. Automated gross motion planning systems may be utilized to simulate the movement of the robot on a computer. However, in industry, automatically generated robot motion plans are seldom (if ever) used because the accuracy of such plans is not trusted and/or because the algorithms used to generate such plans are complicated and time-consuming.
In academics, many sophisticated automated robot motion planning algorithms have been proposed. However, a common focus in academia is to obtain optimal results, i.e., to generate a robot motion plan that moves the robot along the most efficient path from an initial position to a goal position. Since such methods concentrate on the obtention of optimal results, the resulting algorithms tend to be complicated and time-consuming.
5. Definitions
For purposes of clarification, and to assist readers in an understanding of the present invention, a number of terms used herein are defined as follows:
Bending Apparatus/Bending Workstation--a workstation or apparatus for performing modern sheet metal working functions, including bend operations. PA1 Bending Sheets of Malleable Material--working of sheets of malleable material, such as sheet metal, including, but not limited to, up-action air bending, V bending, R bending, hemming, seaming, coining, bottoming, forming, wiping, folding type bending, custom bending and so on. PA1 Maximal Overlapping Rectangloid--a rectangloid with its sides expanded in each orthogonal direction to the maximum possible location within a defined free space, such as described below in the text corresponding to FIG. 11D. PA1 m-Tree Representation of a Work Space--a decomposition of a rectangloid representative of a work space into smaller rectangloids, such decomposition being utilized to represent which portions of the work space rectangloid are empty, full, or mixed. The resulting decomposition being defined in terms of a tree. An example of an octree representation of a work space, which is a type of m-tree representation, is given in FIG. 1 and FIGS. 11A and 11B.
Rectangloid--a rectangle in a two-dimensional space, or a parallelepiped in a three-dimensional space.